//题目:
// 给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
// 下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。
// 在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。
// 具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
#include<iostream>
#include<limits.h>
#include<vector>
#include<map>

using namespace std;
//代码
class Solution 
{
    int ret=INT_MAX;
    map<pair<int,int>,int> dp;//记录从(i,j)位置到终点下降路径的最小值
public:
    // void dfs(const vector<vector<int>>& matrix,int row,int col,int sum)
    // {
    //     if(row==matrix.size()-1){
    //         ret=min(ret,sum);
    //         return;
    //     }
    //     //寻找下一个落脚点
    //     for(int i=-1;i<=1;i++)
    //     {
    //         int x=row+1,y=col+i;
    //         if(x>=0 && x<matrix.size() && y>=0 && y<matrix[0].size())
    //             dfs(matrix,x,y,sum+matrix[x][y]);
    //     }
    // }

    int dfs(const vector<vector<int>>& matrix,int row,int col)
    {
        if(row==matrix.size()) return 0;

        if(dp.count({row,col}))return dp[{row,col}];

        int min_sum=INT_MAX;
        //寻找下一个落脚点,并计算从(row,col)位置出发到达终点路径和的最小值
        for(int i=-1;i<=1;i++)
        {
            int x=row+1,y=col+i;
            if(x>=0 && x<=matrix.size() && y>=0 && y<matrix[0].size())
                min_sum=min(matrix[row][col]+dfs(matrix,x,y),min_sum);
        }
        dp[{row,col}]=min_sum;
        return min_sum;
    }
    int minFallingPathSum(vector<vector<int>>& matrix) 
    {
        //法一：全排列————超时      ×
        // for(int j=0;j<matrix[0].size();j++)
        //     dfs(matrix,0,j,matrix[0][j]);
        // return ret;

        //法二：优化————记忆化搜索   √
        // int ret=INT_MAX;
        // for(int j=0;j<matrix[0].size();j++)
        //     ret=min(ret,dfs(matrix,0,j));
        // return ret;

        //法三：动态规划
        //1.创建dp表————记录从起始位置位置到(i,j)下降路径的最小值
        map<pair<int,int>,int> dp;
        //2.初始化
        for(int j=0;j<matrix[0].size();j++)
            dp[{0,j}]=matrix[0][j];
        //3.填表————dp[{i,j}]=matrix[i][j]+min(dp[{i-1,j-1}],dp[{i-1,j}],dp[{i-1,j+1}])
        for(int i=1;i<matrix.size();i++)
        {
            for(int j=0;j<matrix[0].size();j++)
            {
                int min_value=dp[{i-1,j}];
                if(j-1>=0)
                    min_value=min(min_value,dp[{i-1,j-1}]);
                if(j+1<matrix[0].size())
                    min_value=min(min_value,dp[{i-1,j+1}]);
                dp[{i,j}]=matrix[i][j]+min_value;
            }
        }
        //4.确定返回值
        int ret=INT_MAX;
        for(int j=0;j<matrix[0].size();j++)
            ret=min(ret,dp[{matrix.size()-1,j}]);
        return ret;
    }
};